//1.笨方法--> O(m + log n)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i=0;i<m;++i) {
            int left =0;
            int right = n-1;
            if(!(matrix[i][0]<= target && target <= matrix[i][n-1])) continue;
            while(left <= right) {
                
                int mid = (left+right) >>1;
                if(target>matrix[i][mid])
                    left=mid+1;
                else if(target<matrix[i][mid])
                    right=mid-1;
                else    
                    return true;
                
            }
        }
        return false;
    }
};

//2.将二维数组看成一维数组，因为行列都单增 ---   O(log(m × n))

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int val = matrix[mid / n][mid % n];

            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }

        return false;
    }
};

